package com.github.yangyishe.p200;

import com.github.yangyishe.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 148. 排序链表
 * https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150
 * todo 比较慢,以后有时间再优化
 * <p>
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [-1,5,3,4,0]
 * 输出：[-1,0,3,4,5]
 * 示例 3：
 * <p>
 * 输入：head = []
 * 输出：[]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 链表中节点的数目在范围 [0, 5 * 104] 内
 * -105 <= Node.val <= 105
 * <p>
 * <p>
 * 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 */
public class Problem148 {
    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        int[] nums=new int[]{};
        ListNode head=ListNode.getInstance(nums);

        Problem148 problem148 = new Problem148();
        ListNode listNode = problem148.sortList(head);
        listNode.print();

    }

    /**
     * 思路:
     * 链表形式的排序问题
     * 此处使用归并排序
     * <p>
     * 分: 依次遍历, 每隔2^n个,分为一组.进行排序.n从0开始.直到2^(n+1)>链表数量
     * 治: 对2^n的元素取两组,进行排序并合并一个新的链表
     * <p>
     * 使用链表思考有点费劲, 先将之简化为数组排序.
     *
     * @param head the head
     * @return list node
     */
    public ListNode sortList(ListNode head) {
        ListNode temp=head;
        List<Integer> numList=new ArrayList<>();
        while(temp!=null){
            numList.add(temp.val);
            temp=temp.next;
        }

        Integer[] integers = numList.toArray(new Integer[0]);
        int[] tempArr=new int[integers.length];

        sort(integers,0,integers.length-1,tempArr);

        ListNode result=null;
        for(int i=0;i<integers.length;i++){
            if(i==0){
                temp=new ListNode(integers[i]);
                result=temp;
            }else{
                temp.next=new ListNode(integers[i]);
                temp=temp.next;
            }
        }

        return result;
    }


    /**
     * 分治排序
     * mid 左侧闭区间,右侧开区间
     * @param nums
     * @param start 闭区间
     * @param end 闭区间
     * @param tempArr
     */
    private void sort(Integer[] nums,int start,int end,int[] tempArr){
        if(start<end){
            // 子区间, 左闭右开
            int mid=(start+end)/2;
            sort(nums,start,mid,tempArr);
            sort(nums,mid+1,end,tempArr);

            int left=start;
            int right=mid+1;
            int tempIndex=start;
            while(left<=mid||right<=end){
                if(left>mid){
                    tempArr[tempIndex++]=nums[right++];
                }else if(right>end){
                    tempArr[tempIndex++]=nums[left++];
                }else{
                    if(nums[left]>nums[right]){
                        tempArr[tempIndex++]=nums[right++];
                    }else{
                        tempArr[tempIndex++]=nums[left++];
                    }
                }
            }
            for(int i=start;i<=end;i++){
                nums[i]=tempArr[i];
            }

        }
    }



}
